package linear_list.leetcode.medium;

/**
 * @author bruin_du
 * @description 重排链表
 * @date 2022/8/10 22:30
 **/
public class OfferII026_ReorderList {
    public void reorderList(ListNode head) {
        if (head.next == null || head.next.next == null) return;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode head1 = head, head2 = null;
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head2;
            head2 = cur;
            cur = next;
        }
        while (head2 != null) {
            ListNode next1 = head1.next, next2 = head2.next;
            head1.next = head2;
            head2.next = next1;
            head1 = next1;
            head2 = next2;
        }
    }
}
